package com.jsy.common.leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

class BSTIterator {

    List<TreeNode> list = new ArrayList<>();
    TreeNode initNode = null;
    int current = 0;
    public BSTIterator(TreeNode root) {
        initNode = root;
        current = 0;
        list = new ArrayList<>();
        inorder(initNode,list);
    }
    
    public int next() {
        return list.get(current++).val;
    }
    
    public boolean hasNext() {
        return current < list.size();
    }

    private void inorder(TreeNode root,List<TreeNode> list){
        if (root != null){
            inorder(root.left,list);
            list.add(root);
            inorder(root.right,list);
        }
    }

    private Queue<TreeNode> queue = new LinkedList<>();
    private void inorder2(TreeNode root,List<TreeNode> list){
        if (root!=null){
            queue.offer(root);
        }
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size>0){
                TreeNode node = queue.poll();
                list.add(node);
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
                size--;
            }
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == q || root == p){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if (left == null){
            return right;
        }
        if (right == null){
            return left;
        }
        return root;
    }

    private List<Integer> rightSideViewList;
    private Deque<TreeNode> deque = new LinkedList<>();
    public List<Integer> rightSideView(TreeNode root) {
        rightSideViewList = new ArrayList<>();
        int depth = 0;
//        dfs(root,depth);
        if (root != null){
            deque.offer(root);
        }
        while (!deque.isEmpty()){
            int size = deque.size();
            while (size>0){
                TreeNode poll = queue.poll();
                if (poll.left!=null){
                    deque.offer(poll.left);
                }
                if (poll.right!=null){
                    deque.offer(poll.right);
                }
                if (size==1){
                    rightSideViewList.add(poll.val);
                }
                size--;
            }
            depth++;
        }
        return rightSideViewList;
    }
    private void dfs(TreeNode root,int depth) {
        if (root == null){
            return;
        }
        if (depth == rightSideViewList.size()){
            rightSideViewList.add(root.val);
        }else {
            rightSideViewList.set(depth,root.val);
        }
        System.out.println(depth);
        dfs(root.left,depth+1);
        dfs(root.right,depth+1);
    }

    private List<Double> averageOfLevels;
    public List<Double> averageOfLevels(TreeNode root) {
        averageOfLevels = new ArrayList<>();
        int depth = 0;
        if (root != null){
            deque.offer(root);
        }
        while (!deque.isEmpty()){
            int size = deque.size();
            int devide = size;
            int sum = 0;
            while (size>0){
                TreeNode poll = deque.poll();
                if (poll.left!=null){
                    deque.offer(poll.left);
                }
                if (poll.right!=null){
                    deque.offer(poll.right);
                }
                sum += poll.val;
                size--;
            }
            double average = Math.round(sum*1d / devide);
            averageOfLevels.add(average);
            depth++;
        }
        return averageOfLevels;
    }

    private List<Integer> levelList;
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        int depth = 0;
        if (root != null){
            deque.offer(root);
        }
        while (!deque.isEmpty()){
            int size = deque.size();
            levelList = new ArrayList<>();
            while (size>0){
                TreeNode poll = deque.poll();
                if (poll.left!=null){
                    deque.offer(poll.left);
                }
                if (poll.right!=null){
                    deque.offer(poll.right);
                }
                levelList.add(poll.val);
                size--;
            }
            list.add(levelList);
            depth++;
        }
        return list;
    }

    private Map<Integer,List<Integer>> map = new LinkedHashMap<>();
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        int depth = 0;
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(root,depth,ans,list);
        return ans;
    }
    private void dfs(TreeNode root,int depth,List<List<Integer>> ans,List<Integer> list) {
        if (root == null){
            return;
        }
        if (depth==ans.size()){
            ans.add(new ArrayList<>());
        }
        list = ans.get(depth);
        if (depth % 2 == 0){
            list.add(root.val);
        }else {
            list.add(0,root.val);
        }
        dfs(root.left,depth+1,ans,list);
        dfs(root.right,depth+1,ans,list);
    }

    private int cur = -1;
    private int res = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        res = Integer.MAX_VALUE;
        List<TreeNode> list = new ArrayList<>();
        inorder(root);
        return res;
    }

    private void inorder(TreeNode root){
        if (root != null){
            inorder(root.left);
            if (cur != -1) {
                res = Math.min(res, root.val - cur);
            }
            cur = root.val;
            inorder(root.right);
        }
    }

    public int kthSmallest(TreeNode root, int k) {
        List<Integer> ans = new ArrayList<>();
        inorder3(root,ans);
        k = k%ans.size();
        if (k==0){
            return ans.get(ans.size()-1);
        }
        return ans.get(k-1);
    }

    private void inorder3(TreeNode root, List<Integer> ans) {
        if (root != null){
            inorder3(root.left,ans);
            ans.add(root.val);
            inorder3(root.right,ans);
        }
    }

    private int index = 0;
    private int pre = 0;
    public boolean isValidBST(TreeNode root) {
         if (root == null){
             return true;
         }
        boolean left = isValidBST(root.left);
        if (index==0){
             index++;
             pre = root.val;
         }else {
             if (root.val <= pre){
                 return false;
             }else {
                 pre = root.val;
             }
         }
        boolean right = isValidBST(root.right);
        return left && right;
    }
}